{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Happy Students"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #enumeration #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #枚举 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countWays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #让所有学生保持开心的分组方法数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始、长度为 <code>n</code> 的整数数组 <code>nums</code> ，其中 <code>n</code> 是班级中学生的总数。班主任希望能够在让所有学生保持开心的情况下选出一组学生：</p>\n",
    "\n",
    "<p>如果能够满足下述两个条件之一，则认为第 <code>i</code> 位学生将会保持开心：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>这位学生被选中，并且被选中的学生人数 <strong>严格大于</strong> <code>nums[i]</code> 。</li>\n",
    "\t<li>这位学生没有被选中，并且被选中的学生人数 <strong>严格小于</strong> <code>nums[i]</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回能够满足让所有学生保持开心的分组方法的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,1]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "有两种可行的方法：\n",
    "班主任没有选中学生。\n",
    "班主任选中所有学生形成一组。 \n",
    "如果班主任仅选中一个学生来完成分组，那么两个学生都无法保持开心。因此，仅存在两种可行的方法。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [6,0,3,3,6,7,2,7]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "存在三种可行的方法：\n",
    "班主任选中下标为 1 的学生形成一组。\n",
    "班主任选中下标为 1、2、3、6 的学生形成一组。\n",
    "班主任选中所有学生形成一组。 \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt; nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [happy-students](https://leetcode.cn/problems/happy-students/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [happy-students](https://leetcode.cn/problems/happy-students/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1]', '[6,0,3,3,6,7,2,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        \n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] >= i + 1:\n",
    "                continue\n",
    "            if i == n - 1 or nums[i+1] > i + 1:\n",
    "                ans += 1\n",
    "        \n",
    "        return ans + int(nums[0] > 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = 1\n",
    "        tmp = len(nums)\n",
    "        visited = []\n",
    "        if nums[0] > 0:\n",
    "            ans += 1\n",
    "        while nums:\n",
    "            tmp -= 1\n",
    "            val = nums.pop()\n",
    "            if len(nums):\n",
    "                if nums[-1] < tmp and tmp < val:\n",
    "                    ans += 1\n",
    "                \n",
    "            \n",
    "            \n",
    "        return ans\n",
    "                \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        ans = nums[0] > 0\n",
    "        for i in range(n-2):\n",
    "            if i+1 > nums[i] and i+1 < nums[i+1]:\n",
    "                ans+=1\n",
    "        return ans+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 1 if min(nums) > 0 else 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if (i + 1) > num and (i + 1 >= n or (i + 1) < nums[i+1]):\n",
    "                ans += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        flag = [False] * len(nums)\n",
    "        \n",
    "        for i in range(len(nums) - 1) :\n",
    "            if i+1 > nums[i] and i+1 < nums[i+1] :\n",
    "                ans += 1\n",
    "        \n",
    "        if len(nums) + 1 > nums[-1] :\n",
    "            ans += 1\n",
    "\n",
    "        if nums[0] > 0:\n",
    "            ans += 1\n",
    "        \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        ans, selected = 0, 0\n",
    "        if nums[0] > 0:\n",
    "            ans += 1 \n",
    "        for i in range(len(nums) - 1):\n",
    "            selected += 1\n",
    "            if selected > nums[i] and selected < nums[i + 1]:\n",
    "                ans += 1\n",
    "        if len(nums) > nums[len(nums) - 1]:\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = [0]*(n+1)\n",
    "        for x in nums:\n",
    "            cnt[x] += 1\n",
    "\n",
    "        ans = 0 if  cnt[0] > 0 else 1\n",
    "        sum = 0\n",
    "        for i in range(1, n+1):\n",
    "            sum += cnt[i-1]\n",
    "            if cnt[i] == 0 and i == sum:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        nums = [-1] + nums + [float('inf')]\n",
    "        res = 0\n",
    "        for i, x in enumerate(nums[:-1]):\n",
    "            if i > x and i < nums[i + 1]:\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        print(nums)\n",
    "        cnt = 0\n",
    "        n = len(nums)\n",
    "        \n",
    "        idx_last = -1\n",
    "        for idx, val in enumerate(nums):\n",
    "            if val < idx + 1 and idx+1 == n:\n",
    "                print(\"select all\")\n",
    "                cnt += 1\n",
    "            elif val < idx + 1 and idx + 1 < n and idx + 1 < nums[idx+1]:\n",
    "                \n",
    "                print(\"select\", idx,[idx_last,idx])\n",
    "                cnt += 1\n",
    "                idx_last = idx\n",
    "        if nums[0] != 0: cnt += 1\n",
    "        return cnt\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        tmp=list(range(1,len(nums)+1))\n",
    "        ans=0\n",
    "        for i in range(len(nums)-1):\n",
    "            if tmp[i]>nums[i] and tmp[i]<nums[i+1]:\n",
    "                ans+=1\n",
    "        if nums[0]>0:\n",
    "            ans+=1\n",
    "        if tmp[-1]>nums[-1]:\n",
    "            ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        n = len(nums)\n",
    "        result = 0\n",
    "        print(nums)\n",
    "        if 0 < nums[0]:\n",
    "            result += 1\n",
    "        for i in range(1, n):\n",
    "            if i < nums[i] and i > nums[i - 1]:\n",
    "                result += 1\n",
    "        if n > nums[n - 1]:\n",
    "            result += 1\n",
    "        return result\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        idx = [i+1 for i in range(len(nums))]\n",
    "        cnt = 0\n",
    "        if nums[0]>0:\n",
    "            cnt+=1\n",
    "        \n",
    "        end = 1e5+3\n",
    "        nums.append(end)\n",
    "        \n",
    "        for i in range(len(nums)-1):\n",
    "            if idx[i]>nums[i] and idx[i]<nums[i+1]:\n",
    "                cnt+=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        # print(nums)\n",
    "        t = []\n",
    "        for k, gi in groupby(nums):\n",
    "            cnt = len(list(gi))\n",
    "            t.append((k, cnt))\n",
    "        res = 0\n",
    "        cur = 0\n",
    "        # print(t)\n",
    "        if t[0][0]>0:\n",
    "            res += 1\n",
    "        for i, (k, cnt) in enumerate(t):\n",
    "            cur += cnt\n",
    "            # print(k, cnt, cur)\n",
    "            if cur>k and (i+1>=len(t) or cur<t[i+1][0]):\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        arr = []\n",
    "        res = 0\n",
    "        for i in range(len(nums) + 1):\n",
    "            if i not in s: arr.append(i)\n",
    "        nums.sort()\n",
    "        for x in arr:\n",
    "            l, r = -1, len(nums)\n",
    "            while l + 1 < r:\n",
    "                m = (l + r) // 2\n",
    "                if nums[m] < x: l = m\n",
    "                else: r = m\n",
    "            if r == x: res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        arr = []\n",
    "        res = 0\n",
    "        for i in range(len(nums) + 1):\n",
    "            if i not in s: arr.append(i)\n",
    "        nums.sort()\n",
    "        for x in arr:\n",
    "            l, r = -1, len(nums)\n",
    "            while l + 1 < r:\n",
    "                m = (l + r) // 2\n",
    "                if nums[m] < x: l = m\n",
    "                else: r = m\n",
    "            if r == x: res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        count = 0\n",
    "        n = len(nums)\n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            s.add(nums[i])\n",
    "        # 选择0-n个学生\n",
    "        for i in range(n + 1):\n",
    "            # i必须不能在nums[i]中出现过\n",
    "            if i in s:\n",
    "                continue\n",
    "            # 严格小于i的，必须选中\n",
    "            left = bisect.bisect_right(nums, i)\n",
    "            if i == left:\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countWays(self, nums: List[int]) -> int:\n",
    "        A=set([i for i in range(len(nums)+1)])\n",
    "        for i in range(len(nums)):\n",
    "            A.discard(nums[i])\n",
    "        A=list(A)\n",
    "        nums.sort()\n",
    "        def find(x):\n",
    "            l=-1\n",
    "            r=len(nums)\n",
    "            while r-l>1:\n",
    "                m=(l+r)//2\n",
    "                if nums[m]<x:\n",
    "                    l=m\n",
    "                else:\n",
    "                    r=m\n",
    "            return l+1\n",
    "        c=0\n",
    "        for i in A:\n",
    "            if i==find(i):\n",
    "                c+=1\n",
    "        return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def countWays(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        res=0\n",
    "        if min(nums)>0:\n",
    "            res+=1\n",
    "        c=collections.Counter(nums)\n",
    "        cs=sorted(list(c.keys()))\n",
    "        xuan=[0]*len(cs)\n",
    "        for i,h in enumerate(cs):\n",
    "            xuan[i]=c[h]\n",
    "        for i in range(1,len(cs)):\n",
    "            xuan[i]+=xuan[i-1]\n",
    "        for i in range(len(cs)-1):\n",
    "            if cs[i]<xuan[i] and cs[i+1]>xuan[i]:\n",
    "                res+=1\n",
    "        if cs[-1]<xuan[-1]:\n",
    "            res+=1\n",
    "        return res\n",
    "            \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
